package com.algorithm;

import com.google.common.collect.Lists;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * @program: study
 * @className: SubSet
 * @description: TODO
 * @author: kukuxiahuni
 * @create: 2019-09-19 09:58
 * @version: v1.0
 **/
public class SubSet {

    public static void main(String[] args) {
        List<List<Integer>> result = subset(Arrays.asList(1, 4, 9));

        result.stream().forEach(
                System.out::println
        );

    }

    /**
     * 功能描述: TODO
     *
     * @param:
     * @return:
     * @auther: kukuxiahuni
     * @date: 2019-09-19 09:59
     * @modify_auther: kukuxiahuni
     * @modify_time: 2019-09-19 09:59
     **/
    private static final List<List<Integer>> subset(
            List<Integer> list) {

        if (list.isEmpty()) {
            List<List<Integer>> ans = new ArrayList<>();
            ans.add(Collections.EMPTY_LIST);
            return ans;
        }

        Integer first = list.get(0);
        List<Integer> rest = list.subList(1, list.size());
        List<List<Integer>> subans = subset(rest);
        List<List<Integer>> subans2 = insertAll(first, subans);
        return concat(subans, subans2);

    }

    /**
     * 功能描述: TODO
     *
     * @param: 1
     * @return:
     * @auther: kukuxiahuni
     * @date: 2019-09-19 10:03
     * @modify_auther: kukuxiahuni
     * @modify_time: 2019-09-19 10:03
     **/
    private static final List<List<Integer>> insertAll(Integer first, List<List<Integer>> lists) {

        List<List<Integer>> result = new ArrayList<>();
        for (List<Integer> list : lists) {
            List<Integer> copyList = new ArrayList<>();
            copyList.add(first);
            copyList.addAll(list);
            result.add(copyList);
        }
        return result;
    }

    private static final List<List<Integer>> concat(List<List<Integer>> a, List<List<Integer>> b) {
        List<List<Integer>> r = new ArrayList<>(a);
        r.addAll(b);
        return r;
    }

}
